package org.eda2;

import java.util.ArrayList;
import java.util.HashMap;

/**
 * Clase RutasBackTracking. Clase que implementa los metodos para calcular las
 * rutas compuestas de usuarios, necesarias para minimizar la cantidad de las
 * mismas, y a su vez minimizar la distancia recorida.
 */

public class RutasBackTracking {

	/**
	 * Atributo de clase nivel. Hace refencia al nivel sobre el arbol de
	 * exploracion
	 */
	int nivel = 1;

	/**
	 * Atributo de clase nRutasOptima. Hace referencia al numero de dias(rutas)
	 * necesario para inspeccionar a los usuarios.
	 */
	int nRutasOptima = Integer.MAX_VALUE;

	/**
	 * Atributo de clase. Hace referencia al numero de dias(rutas) de la
	 * solucion actual investigada.
	 */
	int nRutasActual = 1;

	/**
	 * Atributo de clase. Hace referencia a la distancia total de nuestra
	 * solucion.
	 */
	int distanciaOptima = Integer.MAX_VALUE;

	/**
	 * Atributo de clase. Hace referencia a la distancia de nuestra solucion
	 * actual investigada.
	 */
	int distanciaActual = 0;

	/**
	 * Atributo de clase. Hace referencia al tiempo de inspeccion de los
	 * usuarios actuales inspeccionados.
	 */
	int tiempo = 0;

	/**
	 * Atributo de clase. Hace referencia al total de bloques de tiempo de 15
	 * minutos de una jornada de inspeccion factible sin excederse.
	 */
	final int bloquesTiempoJornada = 26;

	/**
	 * Atributo de clase. Hace referencia a la lista solucion optima de nuestro
	 * problema. Es la solucion.
	 */
	ArrayList<User> optima = new ArrayList<User>();

	/**
	 * Atributo de clase. Hace referencia a la lista solucion actual estiduada.
	 * Puede llegar a formar parte de la solucion.
	 */
	ArrayList<User> actual = new ArrayList<User>();

	/**
	 * Atributo de clase. Hace referencia a la estructura de nuestra solucion
	 * actual.
	 */
	int[] estado = null;

	/** Atributo de clase. Hace referencia a la avenida de los usuarios. */
	int avenidaTaller;

	/** Atributo de clase. Hace referencia a la calle de los usuarios. */
	int calleTaller;

	/**
	 * Atributo de clase. Hace referencia a cuando un usuario es el ultimo de
	 * una jornada o ruta.
	 */
	boolean[] finDeRuta = null;

	/**
	 * Atributo de clase. Hace referencia a los usuarios a inspeccionar para
	 * formar las rutas.
	 */
	ArrayList<User> usuariosAInspeccionar = null;

	/**
	 * Metodo calcularRutas. Metodo que calcula las rutas compuestas por
	 * usuarios, para optimizar la inspeccion, donde el primer objetivo es
	 * obtener el minimo numero de rutas y entre estas, las que menor distancia
	 * recorran para dicha inspeccion de usuarios.
	 * 
	 * @param usuariosAInspeccionar
	 *            , variable de tipo ArrayList<User>. Hace referencia a los
	 *            usuarios a inspeccionar iniciales.
	 * @param avenidaTaller
	 *            , variable de tipo int. Hace referencia al numero de avenidas
	 *            de mi ciudad.
	 * @param calleTaller
	 *            , variable de tipo int. Hace referencia al numero de calles de
	 *            mi ciudad.
	 * @return
	 */
	public HashMap<Integer, ArrayList<User>> calcularRutas(
			ArrayList<User> usuariosAInspeccionar, int avenidaTaller,
			int calleTaller) {

		HashMap<Integer, ArrayList<User>> solucion = new HashMap<Integer, ArrayList<User>>();
		this.avenidaTaller = avenidaTaller;
		this.calleTaller = calleTaller;
		this.usuariosAInspeccionar = usuariosAInspeccionar;

		inicializarEstructurasAuxiliares();

		while (nivel >= 1) {
			generar();

			if ((nivel == estado.length && criterio())) {
				// Actualizamos optimo...
				this.distanciaOptima = this.distanciaActual;
				this.nRutasOptima = this.nRutasActual;
				optima.clear();
				optima.addAll(actual);
			}

			if (criterio() && nivel < estado.length) {
				// Si hay mas niveles
				nivel = nivel + 1;
			} else {
				// Sino hay mas niveles...
				while (nivel > 0 && !masHermanos()) {
					retroceder();
				}
			}
		}
		estructurarSolucion(solucion);
		return solucion;
	}

	/**
	 * Metodo estructurarSolucion. Metodo que almacena en una estructura de
	 * datos(Mapa), el resultado de la solucion, tanto si hay una unica
	 * solucion, como si hay mas de una.
	 * 
	 * @param solucion
	 *            , variable de tipo HashMap<Integer,ArrayList<User>>. Hace
	 *            referencia a la estructura de datos para guardar nuestra
	 *            solucion.
	 */
	@SuppressWarnings({ "unchecked" })
	private void estructurarSolucion(HashMap<Integer, ArrayList<User>> solucion) {
		ArrayList<User> auxiliar = new ArrayList<User>();
		int tiempoAux = 0;
		for (int i = 0; i < nRutasOptima - 1; i++) {
			auxiliar.clear();
			while (tiempoAux < bloquesTiempoJornada && optima.size() > 0) {
				tiempoAux += optima.get(0).getTiempoInspec();
				auxiliar.add(optima.remove(0));
			}
			tiempoAux = 0;
			solucion.put(i, (ArrayList<User>) auxiliar.clone());
		}
	}

	/**
	 * Metodo inicializarEstructurasAuxiliares. Metodo que inicializar las dos
	 * estructuras auxiliares que utilizamos, el array d estado y el de
	 * finDeRuta.
	 */
	private void inicializarEstructurasAuxiliares() {
		estado = new int[usuariosAInspeccionar.size()];
		finDeRuta = new boolean[usuariosAInspeccionar.size()];
		for (int i = 0; i < estado.length; i++) {
			estado[i] = -1;
			finDeRuta[i] = false;
		}
	}

	/**
	 * Metodo retroceder. Metodo que realiza la vuelta atras sobre el arbol de
	 * exploracion, anulando las distncias del ultimo, y reseteando los valores
	 * de la estructura de control, y reduciendo el nivel.
	 */
	private void retroceder() {
		// Eliminamos la distancia del ultio usuario....
		distanciaActual = distanciaActual
				- distancia(usuariosAInspeccionar.get(estado[nivel - 1]));

		// Si es final de ruta...
		if (finDeRuta[nivel - 1] == true) {
			tiempo = 0;
			// Recalculamos el tiempo...
			for (int i = nivel - 1;; i--) {
				if (finDeRuta[i] == false) {
					tiempo += actual.get(i).getTiempoInspec();
				} else
					break;
			}
			finDeRuta[estado[nivel - 1]] = false;
			nRutasActual--;

		} else {
			// Sino es final de ruta...
			tiempo = tiempo - actual.get(nivel - 1).getTiempoInspec();
		}
		// Reseteamos
		estado[nivel - 1] = -1;

		// Reducimos nivel...
		nivel--;

		// Eliminamos el usuarior anterior
		actual.remove(actual.size() - 1);
	}

	/**
	 * Metodo masHermanos. Metodo que comprueba que no existen mas hermanos a
	 * generar del nodo.
	 * 
	 * @return bariable de tipo boolean.
	 */
	private boolean masHermanos() {
		return estado[nivel - 1] + 1 < estado.length;
	}

	/**
	 * Metodo criterio. Metodo que comprueba que la lista de usuarios actual no
	 * existen repetidos, y ademas que no sobrepasamos con la lista actual el
	 * numero de rutas optima, y si es asi, tampoco sobrepasamos la distancia.
	 * 
	 * @return variable de tipo boolean.
	 */
	private boolean criterio() {
		// Condicion de factibilidad...
		for (int i = 0; i < nivel - 1; i++) {
			if (estado[nivel - 1] == estado[i]) {
				return false;
			}
		}
		// Condicion de poda...
		if (nRutasActual <= nRutasOptima) {
			if (nRutasActual < nRutasOptima) {
				return true;
			} else if (distanciaActual < distanciaOptima) {
				return true;
			}
		}
		return false;
	}

	/**
	 * Metodo generar. Metodo que realiza la exploracion en profundidad por el
	 * arbol de exploracion, insertando un nuevo usuario a inspeccionar en
	 * nuestra solucion actual.
	 */
	private void generar() {
		estado[nivel - 1] = estado[nivel - 1] + 1;
		// Si no habia usuario de este nivel...
		if (estado[nivel - 1] == 0) {
			distanciaActual = distanciaActual
					+ distancia(usuariosAInspeccionar.get(estado[nivel - 1]));
			actual.add(usuariosAInspeccionar.get(estado[nivel - 1]));
			if ((tiempo + usuariosAInspeccionar.get(estado[nivel - 1])
					.getTiempoInspec()) <= bloquesTiempoJornada) {
				tiempo = tiempo
						+ usuariosAInspeccionar.get(estado[nivel - 1])
								.getTiempoInspec();
			} else {
				tiempo = usuariosAInspeccionar.get(estado[nivel - 1])
						.getTiempoInspec();
				finDeRuta[estado[nivel - 1]] = true;
				nRutasActual++;
			}
		} else {
			// Si habia usuario de este nivel...
			distanciaActual = distanciaActual
					+ distancia(usuariosAInspeccionar.get(estado[nivel - 1]))
					- distancia(actual.get(actual.size() - 1));
			if (tiempo
					+ usuariosAInspeccionar.get(estado[nivel - 1])
							.getTiempoInspec()
					- actual.get(actual.size() - 1).getTiempoInspec() <= bloquesTiempoJornada) {
				tiempo = tiempo
						+ usuariosAInspeccionar.get(estado[nivel - 1])
								.getTiempoInspec()
						- actual.get(actual.size() - 1).getTiempoInspec();
			} else {
				tiempo = usuariosAInspeccionar.get(estado[nivel - 1])
						.getTiempoInspec();
				finDeRuta[estado[nivel - 1]] = true;
				nRutasActual++;
			}
			actual.remove(actual.size() - 1);
			actual.add(usuariosAInspeccionar.get(estado[nivel - 1]));
		}
	}

	/**
	 * Metodo distancia. Metodo que devuelve la distancia entre el usuario
	 * pasado por parametro y el anterior usuario en nuestra lista de usuarios a
	 * inspeccionar.
	 * 
	 * @param user
	 *            , variable de tipo User. Hace referencia al usuario sobre el
	 *            que queremos realizar los calculos de distancia a su anterior.
	 * @return variable de tipo int.
	 */
	private int distancia(User user) {
		if (actual.size() == 0) {
			return (Math.abs(avenidaTaller - user.getAvenida()) + Math
					.abs(calleTaller - user.getCalle()));
		}
		return (Math.abs(actual.get(actual.size() - 1).getAvenida()
				- user.getAvenida()) + Math.abs(actual.get(actual.size() - 1)
				.getCalle() - user.getCalle()));
	}

	/**
	 * Metodo asignarDirecciones. Metodo que asigna aleatoriamente a nuestra
	 * lista de usuarios, un valor para los atributos avenida y calle de la
	 * clase User
	 * 
	 * @param usuariosAInspeccionar
	 *            , variable de tipo ArrayList<User>. Hace referencia a la lista
	 *            de usuarios a inspeccionar.
	 * @param nAvenidas
	 *            , variable de tipo int. Hace referencia al numero maximo de
	 *            avenidas que posee nuestra ciudad.
	 * @param nCalles
	 *            , variable de tipo int. Hace referencia al numero maximo de
	 *            calles que posee nuestra ciudad.
	 */
	public void asignarDirecciones(ArrayList<User> usuariosAInspeccionar,
			int nAvenidas, int nCalles) {
		for (int i = 0; i < usuariosAInspeccionar.size(); i++) {
			int avenida = (int) ((Math.random() * (nAvenidas - 1)) + 1);
			int calle = (int) ((Math.random() * (nCalles - 1)) + 1);
			usuariosAInspeccionar.get(i).setAvenida(avenida);
			usuariosAInspeccionar.get(i).setCalle(calle);
		}
	}
}
